package com.origin.niuke.dynamic;

/**
 * 打家劫舍(二)
 * 算法：动态规划 + 分类讨论
 * 房子首尾相连, 分类讨论
 * 1、偷第一间房, 则最后一间房不能偷
 * 2、不偷第一间房, 则最后一间房可以偷
 *
 * @author yezh
 * @date 2023/1/10 22:06
 */
public class NC177 {

    public int rob(int[] nums) {
        // write code here
        int n = nums.length;
        return Math.max(dynamic(nums, 0, nums[0], n - 1), dynamic(nums, 0, 0, n));
    }

    int dynamic(int[] nums, int a, int b, int n) {
        for (int i = 1; i < n; i++) {
            int tmp = a + nums[i];
            a = b;
            b = Math.max(tmp, b);
        }
        return b;
    }

}
